package com.nanbei.divideandconqure;

/**
 * @ClassDescription: 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xⁿ ）。 （分而治之）
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/11 17:10
 */
public class PowxN {
    public static void main(String[] args) {
        System.out.println(myPow(2, 16));
    }

    public static double myPow(double x, int n) {
        long p = n;

        if (n < 0) {
            p = -n;
        }
        double pow = pow(x, p);
        return n < 0 ? 1 / pow : pow;
    }

    public static double pow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        double p = pow(x, n / 2);
        if ((n & 1) == 1) {
            // 奇数
            return x * p * p;
        } else {
            return p * p;
        }
    }
}
